// 链表 Linked list
// 1.以节点的方式来存储
// 2.每个节点包含data域 next域：指向下一个节点
// 3.链表的各个节点不一定是连续存储
// 4.链表分带头节点链表和没有头节点的链表

// 带头单向链表
class SingleLinkedList {
    // 头节点不要动 不存放具体数据
    head = new HeroNode(0, '', '')

    /**
     *  添加节点
     * @param heroNode {HeroNode}
     */
    add (heroNode) {
        let temp = this.head
        // 找到链表的最后一个节点
        while (true) {
            if (temp.next == null) {
                break
            }
            temp = temp.next
        }
        temp.next = heroNode
    }

    /**
     *  按no顺序添加
     * @param heroNode {HeroNode}
     */
    addByOrder (heroNode) {
        let temp = this.head
        let flag = false // 添加的编号是否存在

        while (true) {
            if (temp.next === null) { // 说明已经在链表的最后
                break
            }
            if (temp.next.no > heroNode.no) { // 找到位置
                break
            } else if (temp.next.no === heroNode.no) { // 说明编号存在
                flag = true
                break
            }
            temp = temp.next
        }
        if (flag) {
            console.log('编号已经存在')
        } else {
            heroNode.next = temp.next
            temp.next = heroNode
        }
    }

    /**
     * 根据NO修改节点信息
     * @param newHeroNode {HeroNode}
     */
    update (newHeroNode) {
        if (this.head.next === null) {
            console.log('链表为空')
            return
        }
        let temp = this.head.next
        let flag = false // 是否找到该节点
        while (true) {
            if (temp === null) {
                break
            }
            if (temp.no === newHeroNode.no) {
                flag = true
                break
            }
            temp = temp.next
        }
        if (flag) {
            temp.name = newHeroNode.name
            temp.nickname = newHeroNode.nickname
        } else {
            console.log('没有找到该节点')
        }
    }

    /**
     * 根据no删除节点
     * @param no {number}
     */
    delete (no) {
        if (this.head.next === null) {
            console.log('链表为空')
            return
        }
        let temp = this.head
        let flag = false // 是否找到该节点
        while (true) {
            if (temp.next === null) {
                break
            }
            if (temp.next.no === no) {
                flag = true
                break
            }
            temp = temp.next
        }
        if (flag) {
            temp.next = temp.next.next
        } else {
            console.log('没有找到该节点')
        }
    }

    // 显示链表
    list () {
        if (this.head.next === null) {
            console.log('链表为空')
            return
        }
        let temp = this.head.next
        while (true) {
            if (temp === null) {
                break
            }
            console.log(temp.toString())
            temp = temp.next
        }
    }

    head () {
        return this.head
    }
}

class HeroNode {
    no = ''
    name = ''
    nickname = ''
    next = null

    /**
     *
     * @param no {number}
     * @param name {string}
     * @param nickname {string}
     */
    constructor (no, name, nickname) {
        this.no = no
        this.name = name
        this.nickname = nickname
    }

    toString () {
        return `HeroNode [no=${this.no},name=${this.name},nickname=${this.nickname}]`
    }
}

/**
 * 获取单向链表有效节点个数
 * @param head
 */
function getLength (head) {
    if (head.next === null) { // 空链表
        return 0
    }
    let length = 0
    let temp = head.next
    while (temp !== null) {
        length++
        temp = temp.next
    }
    return length
}

// 查找单链表中的倒数第k个节点
function findLastIndexNode (head, index) {
    if (head.next === null) { // 空链表
        return null
    }
    let size = getLength(head)
    if (index <= 0 || index > size) {
        return null
    }
    let cur = head.next
    for (let i = 0; i < size - index; i++) {
        cur = cur.next
    }
    return cur
}

// 单链表反转
function reverseList (head) {
    if (head.next === null || head.next.next === null) { // 无需反转
        return head
    }
    let cur = head.next
    let next = null
    let reverseHead = new HeroNode(0, '', '')
    while (cur !== null) {
        next = cur.next
        cur.next = reverseHead.next
        reverseHead.next = cur
        cur = next
        console.log('reverseHead', reverseHead)
    }
    head.next = reverseHead.next
    return head
}

function main () {
    let hero1 = new HeroNode(1, '宋江', '及时雨')
    let hero2 = new HeroNode(2, '卢俊义', '玉麒麟')
    let hero3 = new HeroNode(3, '吴用', '智多星')
    let hero4 = new HeroNode(4, '林冲', '豹子头')

    let singleLinkedList = new SingleLinkedList()
    // singleLinkedList.add(hero1)
    // singleLinkedList.add(hero2)
    // singleLinkedList.add(hero3)
    // singleLinkedList.add(hero4)
    // singleLinkedList.list()

    console.log('顺序添加测试')
    singleLinkedList.addByOrder(hero3)
    singleLinkedList.addByOrder(hero4)
    singleLinkedList.addByOrder(hero1)
    singleLinkedList.addByOrder(hero2)
    singleLinkedList.list()

    console.log('修改测试')
    singleLinkedList.update(new HeroNode(2, 'A', 'A'))
    singleLinkedList.list()

    console.log('删除测试')
    singleLinkedList.delete(2)
    singleLinkedList.list()

    console.log('单向链表有效节点个数测试')
    let len = getLength(singleLinkedList.head)
    console.log(len)

    console.log('测试-倒数第k个节点')
    console.log(findLastIndexNode(singleLinkedList.head, 1).toString())

    console.log('测试-链表反转')
    reverseList(singleLinkedList.head)
    singleLinkedList.list()
}

main()
